package sort

/*
	平均时间复杂度：O(n^2)
	最好情况：O(n)
	最坏情况：O(n^2)
	空间复杂度：O(1)
	排序方式：Inplace
	稳定性：稳定
*/
func InsertionSort(nums []int) {
	// n := len(nums)

	for i, v := range nums {
		temp := v
		var j int
		for j = i - 1; j >= 0; j-- {
			if nums[j] > temp {
				nums[j+1] = nums[j]
			} else {
				nums[j+1] = temp
				break
			}
		}
		if j == -1 {
			nums[0] = temp
		}
	}
}
